# 归并排序


def merge(arr1, arr2):
    p1 = 0
    p2 = 0
    l = []
    while p1 < len(arr1) and p2 < len(arr2):
        if arr1[p1] > arr2[p2]:
            l.append(arr2[p2])
            p2 += 1
        else:
            l.append(arr1[p1])
            p1 += 1

    # while p1 < len(arr1):
    #     l.append(arr1[p1])
    #     p1+=1
    # while p2 < len(arr2):
    #     l.append(arr2[p2])
    #     p2+=1
    print(p1, p2)
    l += arr1[p1:]
    l += arr2[p2:]
    print(l)


def merge_02(arr1, arr2):
    p1 = 0
    p2 = 0
    l = []
    while len(arr1) > p1 and len(arr2) > p2:
        if arr1[p1] < arr2[p2]:
            l.append(arr1[p1])
            p1 += 1
        else:
            l.append(arr2[p2])
            p2 += 1
    l += arr1[p1:]
    l += arr2[p2:]
    # print(f'l1:{arr1},{p1},\nl2:{arr2},{p2},l:{l}')
    # print(l)
    return l


def merge_sort(arr):
    if len(arr) == 1:
        print(arr)
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    return merge_02(merge_sort(left), merge_sort(right))


if __name__ == '__main__':
    l1 = [1, 3, 5, 7]
    l2 = [2, 4, 6, 8, 9]
    print(merge_02(l1, l2))
    l = [6, 7, 9, 3, 0, 2, 1, 8, 5]
    print(merge_sort(l))
    # print(l[:4],l[4:])
